package com.wyp168.leetcode.treenode;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * @ClassName PrintTree
 * @Description TODO
 * @Author wyp168
 * @Date 2022/8/22 08:20
 */
public class PrintTreeSolution {
    public static void main(String[] args) {

        //构造二叉树
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        a.left = b;
        a.right = c;
        b.right = d;

        PrintTreeSolution printTreeSolution = new PrintTreeSolution();
        List<List<String>> lists = printTreeSolution.printTree(a);
        for (List<String> list : lists) {
            for (String s : list) {
                if (s.equals("")) {
                    System.out.print("\"\"" + ",");
                } else {
                    System.out.print(s + ",");
                }
            }
            System.out.println();
        }


    }

    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> ans = new ArrayList<>();

        //TODO
        int height = getMaxDepth(root, -1);
        //优化边界值判断之只有一个跟节点的情况
        if (height == 0) {
            List<String> list = new ArrayList<>();
            list.add(Integer.toString(root.val));
            ans.add(list);
            return ans;
        }
        //数组的列数和行数
        int col = (int)Math.pow(2, height + 1) - 1;
        int row = height + 1;
        //定义一个二维数组，用来封装打印二叉树内容
        Integer[][] ansArr = new Integer[row][col];

        //调用填充打印方法
        fillTreeVal(ansArr, root, 0, col / 2, height);

        for (int i = 0; i < row; i++) {
            List<String> subStrList = new ArrayList<>();
            for (int j = 0; j < col; j++) {
                if (Objects.isNull(ansArr[i][j])) {
                    subStrList.add("");
                } else {
                    subStrList.add(Integer.toString(ansArr[i][j]));
                }
            }
            ans.add(subStrList);
        }


        return ans;
    }

    //填充打印二维数组中对应位置的二叉树节点值
    public void fillTreeVal(Integer[][] arrStr, TreeNode node, int x, int y, int height) {
        //边界值优化
        if (node == null) {
            return;
        }
        //以当前节点所在的列划分下一行数组，分为左右两个部分，依附于父节点的纵坐标
        arrStr[x][y] = node.val;
        fillTreeVal(arrStr, node.left, x + 1, y - (1 << (height - x - 1)), height);
        fillTreeVal(arrStr, node.right, x + 1, y + (1 << (height - x - 1)), height);
    }

    //获取二叉树的最大深度
    public int getMaxDepth(TreeNode node, int tempMaxDepth) {
        if (node == null) {
            return tempMaxDepth;
        }
        tempMaxDepth ++;
        int leftMaxDepth = getMaxDepth(node.left, tempMaxDepth);
        int rightMaxdepth = getMaxDepth(node.right, tempMaxDepth);

        return Math.max(leftMaxDepth, rightMaxdepth);
    }
}
